package 组合;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author: AirMan
 * @date: 2025/4/10 16:28
 * @description: 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 * 你可以按 任何顺序 返回答案。
 */
public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        // 回溯 backtracking
        // 回溯的参数：n，k，startIndex，全局变量：result记录最后的结果集，path记录当前遍历情况下的路径
        // 回溯的返回值：void
        // 回溯的终止条件：想象为一颗 N 叉树，当寻找到的路径 path 长度为 k 时，就访问到了叶子节点
        //              所有为 path.size() == k
        // 单层回溯遍历过程：
        // 横向遍历：遍历集合
        // 纵向遍历：先处理当前遍历的当前节点，然后开始搜索，搜索完毕进行回溯，撤销处理的节点！

        backTracking(n, k, 1);
        return result;

    }

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public void backTracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            List<Integer> list = new ArrayList<>(path);
            result.add(list);
            return;
        }

        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
            // 处理当前节点
            path.add(i);
            // 回溯搜索
            int pathSize = path.size();
            // 剪枝,只有 pathSize + n - i >= k 满足的时候，才有可能找到 path
            backTracking(n, k, i + 1);
            // 回溯，撤销处理的当前节点
            path.remove(path.size() - 1);
        }
    }
}